home *** CD-ROM | disk | FTP | other *** search
/ FM Towns: Free Software Collection 9 / FM Towns Free Software Collection 9.iso / t_os / tool / pcom / src / lzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  3.0 KB  |  152 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <nslib.h>
  4. #include <pc_inc.h>
  5.  
  6. #define BITS        (14)
  7. #define BITS_        (9)
  8. #define MAX_CODE    ( 16383 )
  9. #define TABLE_SIZE    ( 20011 )
  10. #define BUMP_CODE    ( 256 )
  11. #define EOS            ( 257 )
  12. #define FIRST_CODE    ( 258 )
  13. #define UNUSED        ( -1 )
  14.  
  15. static char *stack;
  16. static DIC *dic;
  17.  
  18.  
  19. static int find_child_node( short parent, short child )
  20. {
  21.     short idx, offset;
  22.  
  23.     idx = ( child << ( BITS - 8 ) ) ^ parent;
  24.     if ( idx == 0 )
  25.         offset = 1;
  26.     else
  27.         offset = TABLE_SIZE - idx;
  28.     for ( ; ; )
  29.         {
  30.         if ( dic[idx].code == UNUSED )
  31.             return( idx );
  32.         if ( dic[idx].parent == parent && dic[idx].ch == (char)child )
  33.             return( idx );
  34.         idx -= offset;
  35.         if ( idx < 0 )
  36.             idx += TABLE_SIZE;
  37.         }
  38. }
  39.  
  40. static int decode_string( int cu, short code )
  41. {
  42.     while ( code > 255 )
  43.         {
  44.         stack[cu++] = dic[code].ch;
  45.         code = dic[code].parent;
  46.         }
  47.     stack[cu++] = (char)code;
  48.     return( cu );
  49. }
  50.  
  51. int lzw_comp( char *src, int n, BIT_FILE *bfp )
  52. {
  53.     short ch, str, next=FIRST_CODE;
  54.     int i, idx, bits=BITS_, bump=512, si=0, ret=0;
  55.  
  56.     if ( ( dic = malloc( sizeof(DIC)*TABLE_SIZE ) ) == NULL )
  57.         return (-1);
  58.  
  59.     for ( i=0; i<TABLE_SIZE; i++ )
  60.         dic[i].code = UNUSED;
  61.     str = (short)src[si++];
  62.  
  63.     while ( si < n )
  64.         {
  65.         ch = (short)src[si++];
  66.         idx = find_child_node( str, ch );
  67.         if ( dic[idx].code != UNUSED )
  68.             str = dic[idx].code;
  69.         else
  70.             {
  71.             if ( next <= MAX_CODE )
  72.                 {
  73.                 dic[idx].code = next++;
  74.                 dic[idx].parent = str;
  75.                 dic[idx].ch = (char)ch;
  76.                 }
  77.             if ( BIT_write_bits( str, bits, bfp ) < bits )
  78.                 goto err;
  79.             ret += bits;
  80.             if ( next >= bump )
  81.                 {
  82.                 if ( BIT_write_bits( BUMP_CODE, bits, bfp ) < bits )
  83.                     goto err;
  84.                 ret += bits;
  85.                 bits++;
  86.                 bump <<= 1;
  87.                 }
  88.             str = ch;
  89.             }
  90.         }
  91.     if ( BIT_write_bits( str, bits, bfp ) < bits ) goto err;
  92.     if ( BIT_write_bits( EOS, bits, bfp ) < bits ) goto err;
  93.     ret += bits*2;
  94.  
  95.     free( dic );
  96.     return ( ret );
  97.  
  98. err:free( dic );
  99.     return (-1);
  100. }
  101.  
  102. int lzw_exp( char *dest, BIT_FILE *bfp )
  103. {
  104.     short ch, new, old, next=FIRST_CODE;
  105.     int count, di=0, bits=BITS_;
  106.     unsigned int ret;
  107.  
  108.     if ( ( dic = malloc( sizeof(DIC)*TABLE_SIZE ) ) == NULL )
  109.         return (0);
  110.     if ( ( stack = malloc( TABLE_SIZE ) ) == NULL )
  111.         { free( dic ); return (0); }
  112.  
  113.     if ( BIT_read_bits( &ret, bits, bfp ) < bits )
  114.         goto end;
  115.     old = (short)ret;
  116.     ch = old;
  117.     dest[di++] = (char)old;
  118.  
  119.     for( ; ; )
  120.         {
  121.         if ( BIT_read_bits( &ret, bits, bfp ) < bits )
  122.             break;
  123.         if ( ( new = (short)ret ) == EOS ) break;
  124.         else if ( new == BUMP_CODE )
  125.             {
  126.             bits++;
  127.             continue;
  128.             }
  129.         else if ( new >= next )
  130.             {
  131.             stack[0] = (char)ch;
  132.             count = decode_string( 1, old );
  133.             }
  134.         else
  135.             count = decode_string( 0, new );
  136.         ch = stack[count-1];
  137.         while ( count > 0 )
  138.             dest[di++] = (char)stack[--count];
  139.         if ( next <= MAX_CODE )
  140.             {
  141.             dic[next].parent = old;
  142.             dic[next].ch = (char)ch;
  143.             next++;
  144.             }
  145.         old = new;
  146.         }
  147.  
  148. end:free( dic );
  149.     free( stack );
  150.     return ( di );
  151. }
  152.